package code1.binary_tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 原题链接：https://leetcode.cn/problems/count-complete-tree-nodes/
 */
public class P222 {

    //求完全二叉树的节点个数

    //利用完全二叉树的性质
    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
        TreeNode leftNode=root.left;
        TreeNode rightNode=root.right;
        int leftDepth=0,rightDepeh=0;
        while(leftNode!=null){      //求左子树深度(一直往左)
            leftNode=leftNode.left;
            leftDepth++;
        }
        while(rightNode!=null){     //求右子树深度(一直往右)
            rightNode=rightNode.right;
            rightDepeh++;
        }
        if(leftDepth==rightDepeh){  //说明是满二叉树
            return (int)Math.pow(2,leftDepth+1)-1;      //满二叉树的性质
        }
        return countNodes(root.left)+countNodes(root.right)+1;
    }


    //层序遍历法
    public int countNodes2(TreeNode root) {
        if(root==null){
            return 0;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        int count=0;
        while(!queue.isEmpty()){
            int size=queue.size();
            count+=size;
            for(int i=0;i<size;i++){
                TreeNode node = queue.poll();
                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
            }
        }
        return count;
    }
}
